package main

import (
	"fmt"
)

//https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
//寻找最长不含有重复字符的子串
//abcabcbb -> abc
//bbbbbbb -> b
//pwwkew -> wke

//根据测试的结果，可以优化
//但最后还是要回来，因为代码不仅有性能，还有易读性和可理解性
//当系统足够大时，数据结构上的性能差异都不一定时关键的，关键的还是io
func lengthOfLongestSubstring(s string) int {
	lastOccurred := make(map[rune]int)
	start := 0
	maxLength := 0

	//为了支持中文，这里不能使用[]byte(s),而应该使用[]rune(s)
	for i, ch := range []rune(s) {
		//fmt.Printf("i=%d, ch=%s\n", i, string(ch))
		if lastI, ok := lastOccurred[ch]; ok && lastI >= start {
			start = lastI + 1
			//fmt.Printf("===》 start=%d, lastI=%d\n", start, lastI)
		}
		if i-start+1 > maxLength {
			maxLength = i - start + 1
			//fmt.Printf("===》 start=%d, maxLength=%d\n", start, maxLength)
		}
		lastOccurred[ch] = i
		//fmt.Println("===》 lastOccurred=%v", lastOccurred)
	}
	return maxLength
}

//var lastOccurred = make([]int, 0xffff)
//
//func lengthOfLongestSubstring(s string) int {
//	//stores last occurred pos+1 .
//	//0 means not seen
//
//	for i := range lastOccurred {
//		lastOccurred[i] = 0
//	}
//
//	start := 0
//	maxLength := 0
//
//	//为了支持中文，这里不能使用[]byte(s),而应该使用[]rune(s)
//	for i, ch := range []rune(s) {
//		//fmt.Printf("i=%d, ch=%s\n", i, string(ch))
//		if lastI := lastOccurred[ch]; lastI > start {
//			start = lastI
//			//fmt.Printf("===》 start=%d, lastI=%d\n", start, lastI)
//		}
//		if i-start+1 > maxLength {
//			maxLength = i - start + 1
//			//fmt.Printf("===》 start=%d, maxLength=%d\n", start, maxLength)
//		}
//		lastOccurred[ch] = i + 1
//		//fmt.Println("===》 lastOccurred=%v", lastOccurred)
//	}
//	return maxLength
//}

func main() {

	fmt.Println(lengthOfLongestSubstring("abcabcbb"))
	fmt.Println(lengthOfLongestSubstring("bbbbb"))
	fmt.Println(lengthOfLongestSubstring("pwwkew"))

	fmt.Println(lengthOfLongestSubstring(""))
	fmt.Println(lengthOfLongestSubstring("b"))
	fmt.Println(lengthOfLongestSubstring("abcdef"))

	fmt.Println(lengthOfLongestSubstring("我爱慕课网"))
	fmt.Println(lengthOfLongestSubstring("一二三二一"))
	fmt.Println(
		lengthOfLongestSubstring("黑化肥挥发发灰会花飞灰化肥挥发发黑会飞花"),
	)
}
